/**
 * 
 */
package algorithm.sort;

import java.util.Arrays;

/**
 * @author lionbule
 *
 */
public class HeapSortV3 {
	public static int[] heap = {2,1,3,6}; 
	
	public static void main(String[] args) {
		HeapSortV3 v = new HeapSortV3();
		v.heapSort(heap);
	}
	
	public void heapSort(int[] a) {
		System.out.println("ԭʼ��:\t"+Arrays.toString(a));
		
		// why begin from n/2?
		// becuase for complete binary tree, n/2 is last non-leaf node,i.e, n/2+1,n/2+2 ...n are all leaf nodes.
		int n = a.length;
		for (int i = n/2; i >=0; i--) {
			heapify(a, i, n);
			System.out.println("HEAP1:\ti="+i+", "+Arrays.toString(a));
		}
		
		
		for (int i = n-1; i >= 1; i--) {
			// swap 0 and i(n-1,n-2,...1)
			swap(a, 0, i);
			// remove the last element, so heap size is i(n-1,n-2,n-3...1)
			heapify(a, 0, i);
			System.out.println("HEAP2:\t"+Arrays.toString(a));
		}
		System.out.println("SORTED:\t"+Arrays.toString(a));
	}
	
	private int leftChild(int i) {
		return 2*i + 1;
	}	
	
	/**
	 * 
	 * @param a
	 * @param i, the indict of array, begin from 0
	 * @param n, the heap size
	 */
	private void heapify(int[] a, int i, int n) {
		int l = leftChild(i);
		int r = l + 1;
		int largest = -1;
		if(l< n && a[l]>a[i]) {
			largest = l;
		}else {
			largest = i;
		}
		
		if(r< n && a[r]> a[largest]) {
			largest = r;
		}
		
		// if largest is not the current node, swap them, recurs to subtree
		if(largest!=i) {
			swap(a,largest,i);
			heapify(a, largest, n);
		}
	}
	
	private void swap(int[] source, int dex1, int dex2) {
		int temp = source[dex1];
		source[dex1] = source[dex2];
		source[dex2] = temp;
	}
}
